1. Technical Field
This invention relates to distributed computing systems, and more particularly to the art of routing messages between computers in a distributed computing system.
2. Description of the Prior Art
A distributed computing system is an arrangement of computers dispersed over a wide geographical area. Individual host computer systems provide data processing services, and are connected together through a network of communication processors and communication lines. The communication processor is typically a minicomputer or special purpose hardware for message switching controlled by a minicomputer. Such processors form the nodes of the network, and the communication lines are the links that interconnect the nodes. A link is a bi-directional communication path that terminates at a single node on either end. Two nodes having a link between them are said to be neighbors. It is impractical to provide direct communication facilities for every pair of nodes on a typical network so that a message conveyed over the network may pass over one or more intermediate links before reaching its destination.
The function of the host computer is to provide data processing service interactively for users who log on remotely using the network to communicate the necessary exchange of messages that makes up an interactive session. The function of the node, including its control computer, is to provide network services. This includes receiving messages from and transmitting messages to distant users who have logged on over the network to a host served by the node, relaying received messages ultimately destined for some distant node, and managing the communication links between the node and each of its neighbors. In some cases, the network function may be performed by a telecommunications software package installed in the host computer in addition to the data processing software. But more typically the network function is off-loaded into separate node hardware. In any event, a user may log on to a distant computer on the network and interact without concern for the network communication activities taking place.
Each message on the network typically is routed independently, with the nodes adapting to changes in network topology. Thus, if a link goes out of service, messages will be routed over available working links, and any user session with a different computer will continue uninterrupted so long as there is some combination of links over which messages can be routed between user and computer.
The routing of messages is an important network management function that typically takes place at control level 3 under the CCITT packet switching protocol nomenclature. In some prior art arrangements this function is performed by a centralized network management computer (manager). Under this arrangement each node notifies the manager as links connected to the node go down (out of service) or come up (in service). The manager can, therefore, maintain an overview of the entire network's operations and can determine the routing that messages should take to minimize the number of links used. The disadvantage of this arrangement is the high degree of dependency on the manager. Thus if the manager is down network operations may be difficult or impossible. For this reason, managers are made highly reliable, by redundant back-up equipment for example, which adds to the expense and complexity of the network.
A more desirable arrangement is to avoid the use of a centralized network manager and to locate the network routing function in each of the network nodes. One possible implementation of this idea is to have the full network routing function in each node. Thus each node receives full network information from every other node. This is not a completely satisfactory solution since the sending and receiving of messages containing routing information to distant nodes meets the same routing difficulties as the sending and receiving of messages containing normal data. In the prior art, this difficulty has been met by providing two different message routing and handling procedures; one for the normal data messages, and another for the routing messages. This leads to considerable complexity in network design. See, for example, "An Overview of the New Routing Algorithm for the ARPANET," J. M. McQuillan, I. Richer, and E. C. Rosen, Proceedings of the Sixth IEEE Data Communications Symposium, November, 1979, which describes the handling of data messages, and "The Updating Protocol of ARPANET's New Routing Algorithm" by E. C. Rosen, pp. 11-19, Computer Networks 4, North Holland Publishing, 1980, which describes the handling of routing messages on the same network.
A better solution is for each node to be concerned only with the routing of messages between itself and its neighbors. Thus, it is not necessary that a node maintain complete information about the operation of the entire network. It is sufficient for the node to maintain only that information necessary to enable the node to move the message toward its ultimate destination. A suitable decision criterion is used, such as traversing the minimum total number of links. Under this arrangement the distinction between data messages and routing messages is reduced, simplifying the network design. Also, there is no centralized responsibility for determining the correct routing of messages. There is, instead, distributed responsibility. Each node assumes responsibility for forwarding messages to the next appropriate node without full knowledge of the present status of the entire network. The total effect achieved is proper message routing in a simplified fashion without reliance on a centralized authority. If a node goes down, other effected nodes will adapt to the changed conditions and the network functions continue.
The preferred routing procedure, or algorithm, is a distributed one. The term algorithm is not here used in its mathematical sense, that is, the application of mathematical steps to result in a numerical result, but is used in its procedural sense, that is, the procedural or method steps to be used to result in the ultimate goal of physically routing message traffic on a computer network.
The preferred routing algorithm is also adaptive. That is, as network conditions change--links go down or come up, nodes go down or come up--the routing is changed as needed to adapt to the new conditions.
An example of a prior art adaptive distributed routing algorithm is given in the article "A Correctness Proof of a Topology Information Maintenance Protocol for a Distributed Computer Network" by W. D. Tajibnapis, Communications of the ACM, July, 1977. Tejibnapis shows a method that selects routing depending on minimum distance, where distance is measured by the number of links traversed or "hops" to the ultimate destination. Each node maintains a distance table containing the hop count, showing the number of links that must be traversed to reach any other node in the network, beginning with each neighbor of the node containing the table. From this distance table, a route table is constructed showing, for each destination node in the network, the outgoing link that will result in the minimum total hop count for that destination node. In the event of a network change, each effected node modifies its internal route table and communicates information from this new table to each of its neighbors.
This prior art technique leads to certain problems. When the neighbor node modifies its distance table in accordance with the new information, situations may occur temporarily where a node appears to be unreachable (isolated) when in fact it can be reached. Further, this information can result in the appearance of a "phantom" node. A node that is, in fact, isolated may appear to be reachable long after its communication links have gone down. Data messages intended for the isolated node are routed from node to node in a futile effort to reach the isolated node and may temporarily interfere with network operation. Additional steps in the prior art procedure are needed to identify and eliminate such phantom nodes. These additional steps require the exchange of a number of additional routing messages, further occupying network resources.